# 168. 倍数问题
# https://www.lanqiao.cn/problems/168/learning/?page=1&first_category_id=1&second_category_id=3
# Date: 2025/2/13
from collections import defaultdict


def get_max_k_fold(arr, k):
    arr.sort()
    remainders = defaultdict(list)  # 余数: [数字的id]
    for num in arr:
        remainders[num % k].append(num)

    max_sum = 0

    for r1 in remainders.keys():
        for r2 in remainders.keys():
            r3 = k - ((r1 + r2) % k)
            if r3 not in remainders.keys():
                continue
            if r1 == r2 == r3:
                if len(remainders[r1]) >= 3:
                    s = sum(remainders[r1][-3:-1])
                    max_sum = max(max_sum, s)
            elif r1 == r2:
                if len(remainders[r1]) >= 2:
                    s = sum(remainders[r1][-2:]) + remainders[r3][-1]
                    max_sum = max(max_sum, s)
            elif r1 == r3:
                if len(remainders[r1]) >= 2:
                    s = sum(remainders[r1][-2:]) + remainders[r2][-1]
                    max_sum = max(max_sum, s)
            elif r2 == r3:
                if len(remainders[r2]) >= 2:
                    s = sum(remainders[r2][-2:]) + remainders[r1][-1]
                    max_sum = max(max_sum, s)
            else:
                max_sum = max(max_sum, remainders[r1][-1] + remainders[r2][-1] + remainders[r3][-1])

    return max_sum


def get_max_k_fold_opt(arr, k):
    dp = [[-1] * k for _ in range(4)]
    dp[0][0] = 0  # 没选数时，和为 0
    for x in arr:
        # 对于当前 x，我们从已选数量较多的状态倒着更新
        # 遍历 j 从 2 到 0
        r_x = x % k
        for j in range(2, -1, -1):
            for r in range(k):
                if dp[j][r] != -1:
                    new_r = (r + r_x) % k
                    dp[j + 1][new_r] = max(dp[j + 1][new_r], dp[j][r] + x)

    return dp[3][0]


if __name__ == '__main__':
    # n, k = map(int, input().split())
    # inp = list(map(int, input().split()))
    inp = [1, 2, 3, 4]
    print(get_max_k_fold(inp, 3))  # 9
    print(get_max_k_fold_opt(inp, 3))  # 9

    inp = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    print(get_max_k_fold(inp, 5))  # 20
    print(get_max_k_fold_opt(inp, 5))  # 20

    with open("../data/168.in", "r") as file:
        n, k = map(int, file.readline().split())
        inp = list(map(int, file.readline().split()))
    print(get_max_k_fold(inp, k))
    print(get_max_k_fold_opt(inp, k))
